{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这是一种特殊的技巧。使用数组 `hash[26]` 或者 `hash[10]` 来保存某个字母或者数字出现的次数/是否曾经出现过；使用 `hash[256]` 来保存某个ASCII码字符是否出现过，`exist[10000]`、`cnt[10000]`同理。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有一种很特殊的情况，Flag有效和无效节点，统计，LinkNode，Sort。这种情况我们怎么实现呢？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, value=0, is_valid=True):\n",
    "        self.value = value\n",
    "        self.is_valid = is_valid\n",
    "        self.next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "def cmp(a, b):\n",
    "    # 如果a无效，返回1使得a排在b后面\n",
    "    # 如果b无效，返回-1使得b排在a后面\n",
    "    # 如果a和b都有效，根据值排序\n",
    "    if not a.is_valid:\n",
    "        return 1\n",
    "    if not b.is_valid:\n",
    "        return -1\n",
    "    if a.value < b.value:\n",
    "        return -1\n",
    "    elif a.value > b.value:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "# 假设我们有一个链表的头节点head\n",
    "# 我们需要对这个链表进行排序\n",
    "def sort_linked_list(head):\n",
    "    nodes = []\n",
    "    current = head\n",
    "    while current:\n",
    "        nodes.append(current)\n",
    "        current = current.next\n",
    "    \n",
    "    # 使用Python内置的排序函数，并传入自定义的比较函数\n",
    "    nodes.sort(key=lambda x: (not x.is_valid, x.value), reverse=False)\n",
    "    \n",
    "    # 重新连接链表\n",
    "    for i in range(len(nodes)-1):\n",
    "        nodes[i].next = nodes[i+1]\n",
    "    nodes[-1].next = None\n",
    "    return nodes[0]  # 返回新链表的头节点\n",
    "\n",
    "# 创建链表并进行排序\n",
    "head = ListNode(3, True)\n",
    "head.next = ListNode(1, False)\n",
    "head.next.next = ListNode(2, True)\n",
    "head.next.next.next = ListNode(4, False)\n",
    "\n",
    "sorted_head = sort_linked_list(head)\n",
    "\n",
    "# 打印排序后的链表\n",
    "current = sorted_head\n",
    "while current:\n",
    "    print(current.value if current.is_valid else 'Invalid', end=' -> ')\n",
    "    current = current.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个更加好的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value, flag=False):\n",
    "        self.value = value\n",
    "        self.flag = flag\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"Node(value={self.value}, flag={self.flag})\"\n",
    "\n",
    "# 示例数据：节点列表\n",
    "nodes = [\n",
    "    Node(10, False),  # 无效节点\n",
    "    Node(3, True),    # 有效节点\n",
    "    Node(8, False),   # 无效节点\n",
    "    Node(1, True),    # 有效节点\n",
    "    Node(5, True),    # 有效节点\n",
    "]\n",
    "\n",
    "# 统计有效节点的个数\n",
    "cnt = sum(node.flag for node in nodes)\n",
    "\n",
    "# 自定义排序函数：优先按 flag 排序，flag=True 的排在前，value 按升序排\n",
    "nodes.sort(key=lambda x: (not x.flag, x.value))\n",
    "\n",
    "# 取出前 cnt 个有效节点\n",
    "valid_nodes = nodes[:cnt]\n",
    "\n",
    "# 输出排序后的节点列表\n",
    "print(\"排序后所有节点：\", nodes)\n",
    "print(\"有效节点：\", valid_nodes)\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
